#ifndef SKIPLIST_H
#define SKIPLIST_H

/**
 * 参考：W. Pugh, "Skip lists: A probabilistic alternative to balanced trees,"Commun. ACM, pp. 668–676, 1990.
 */

#include <cstdlib>
#include <vector>
#include <ctime>

/**
 * (1) 建议：LEVEL = log2(N)，N为数据规模
 * (2) 键类型KEY应为可比较类型
 */

// SkipList节点类型
template <typename KEY, typename VAL, unsigned LEVEL>
struct SkipNode 
{
    KEY key;
    VAL val;

    // MaxLevel + 1, 下标从1到MaxLevel
    SkipNode<KEY, VAL, LEVEL> *forward[LEVEL + 1];

    void init()
    {
        // 初始化前向指针
        for (unsigned i = 0; i < LEVEL + 1; ++i)
        {
            forward[i] = nullptr;
        }
    }

    // 无参数构造
    SkipNode() : key(KEY()), val(VAL()) { init(); }

    // 键构造
    explicit SkipNode(KEY key_) : key(key_), val(VAL()) { init(); }

    // 键值构造
    SkipNode(KEY key_, const VAL& value_) : key(key_), val(value_) { init(); }
};

// SkipList
template <typename KEY, typename VAL, unsigned LEVEL>
class SkipList 
{
public:
    // 节点类型
    using Node = SkipNode<KEY, VAL, LEVEL>;

    /*
     * 设置KEY界限的意义：简化算法复杂度
     */

    SkipList(KEY min_key, KEY max_key) 
    {
        // 随机种子
        srand(static_cast<unsigned>(time(0)));

        // 链表首/尾节点（不会访问首尾节点，值不重要）
        _head = new Node(min_key);
        _tail = new Node(max_key);

        // 连接首/尾节点所有前向指针
        for (unsigned i = 1; i <= LEVEL; ++i) 
        {
            _head->forward[i] = _tail;
        }
    }

    ~SkipList() 
    {
        // 从第1层逐个删除节点（第一层表现为普通链表）
        Node* current = _head->forward[1];

        while (current != _tail) 
        {
            Node* temp = current;
            current = current->forward[1];
            delete temp;
        }

        // 删除首/尾节点
        delete _head;
        delete _tail;
    }

    // 搜索节点
    const Node* search(KEY search_key) const 
    {
        // 键范围判定
        if (search_key <= _head->key || search_key >= _tail->key)
        {
            return nullptr;
        }

        /*
         * 参考: Figure2. Skip List Search Algorithm
         */
        Node* x = _head;

        for (unsigned i = _level; i >= 1; --i) 
        {
            while (x->forward[i]->key < search_key) 
            {
                x = x->forward[i];
            }
        }
        x = x->forward[1];

        if (x->key == search_key) {
            return x;
        } else {
            return nullptr;
        }
    }

    // 插入节点
    Node* integrate(KEY search_key, const VAL& new_value) 
    {
        // 键范围判定
        if (search_key <= _head->key || search_key >= _tail->key)
        {
            return nullptr;
        }

        /*
         * 参考: Figure4. Skip List Insertion and Deletion Algorithms
         */
        Node* update[LEVEL + 1];
        Node* x = _head;

        for (unsigned i = _level; i >= 1; --i) 
        {
            while (x->forward[i]->key < search_key) 
            {
                x = x->forward[i];
            }
            update[i] = x;
        }
        x = x->forward[1];

        if (x->key == search_key) 
        {
            x->val = new_value;
        } 
        else 
        {
            unsigned new_level = randomLevel();

            if (new_level > _level) 
            {
                for (unsigned i = _level + 1; i <= new_level; ++i) 
                {
                    update[i] = _head;
                }
                _level = new_level;
            }

            x = new Node(search_key, new_value);
            _size++;

            for (unsigned i = 1; i <= new_level; ++i) 
            {
                x->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = x;
            }
        }
        return x;
    }

    // 移除元素
    void remove(KEY search_key) 
    {
        // 键范围判定
        if (search_key <= _head->key || search_key >= _tail->key)
        {
            return;
        }

        /*
         * 参考: Figure4. Skip List Insertion and Deletion Algorithms
         */
        Node* update[LEVEL + 1];
        Node* x = _head;

        for (unsigned i = _level; i >= 1; --i) 
        {
            while (x->forward[i]->key < search_key) 
            {
                x = x->forward[i];
            }
            update[i] = x;
        }
        x = x->forward[1];

        if (x->key == search_key) 
        {
            for (unsigned i = 1; i <= _level; ++i) 
            {
                if (update[i]->forward[i] != x) 
                    break;

                update[i]->forward[i] = x->forward[i];
            }
            delete x;
            _size--;

            while (_level > 1 && _head->forward[_level] == _tail) 
            {
                _level--;
            }
        }
    }

    // 链表 --> 有序向量 
    void toVector(std::vector<Node*> &vec) 
    {
        vec.clear();

        // 遍历第一层
        Node* node = _head->forward[1];
        while (node != _tail) 
        {
            vec.emplace_back(node);
            node = node->forward[1];
        }
    }

    // 获取节点数量
    unsigned size() const 
    {
        return _size;
    }

    // 获取链表头部指针
    const Node* head() const 
    {
        return _head;
    }

    // 获取链表尾部指针
    const Node* tail() const 
    {
        return _tail;
    }

    // 链表 --> 有序向量，且满足： left_key <= vec[i]->key <= right_key
    void toVector(std::vector<Node*> &vec, KEY left_key, KEY right_key) 
    {
        vec.clear();

        if (left_key > right_key)
            return;

        Node* x = _head;
        for (unsigned i = _level; i >= 1; --i) 
        {
            while (x->forward[i]->key < left_key) 
            {
                x = x->forward[i];
            }
        }
        x = x->forward[1];

        while (x->key <= right_key) 
        {
            vec.emplace_back(x);
            x = x->forward[1];
        }
    }

private:
    // 链表首尾指针
    Node* _head = nullptr;
    Node* _tail = nullptr;

    // 当前最大层数
    unsigned _level = 1;

    // 元素个数
    unsigned _size = 0;

    /*
     * 参考: Figure5. Algorithm to Calculate a Random Level 
     * P = 0.5
     */
    unsigned randomLevel() 
    {
        unsigned new_level = 1;
        while (rand() % 2 == 0) 
        {
            new_level++;
        }
        return (new_level < LEVEL) ? new_level : LEVEL;
    }
};



#endif // SKIPLIST_H
